0881. 救生艇【中等】
1. 📝 题目描述
给定数组 people。people[i]表示第 i 个人的体重，船的数量不限，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数。
示例 1：
输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)1
2
3
2
3
示例 2：
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)1
2
3
2
3
示例 3：
输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)1
2
3
2
3
提示：
1 <= people.length <= 5 * 10^41 <= people[i] <= limit <= 3 * 10^4
2. 🎯 s.1 - 贪心 + 双指针
c
int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }
int numRescueBoats(int* people, int peopleSize, int limit) {
qsort(people, peopleSize, sizeof(int), cmp);
int lo = 0, hi = peopleSize - 1, boats = 0;
while (lo <= hi) {
if (people[lo] + people[hi] <= limit) lo++;
hi--;
boats++;
}
return boats;
}1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
js
/**
* @param {number[]} people
* @param {number} limit
* @return {number}
*/
var numRescueBoats = function (people, limit) {
people.sort((a, b) => a - b)
let lo = 0,
hi = people.length - 1,
boats = 0
while (lo <= hi) {
if (people[lo] + people[hi] <= limit) lo++
hi--
boats++
}
return boats
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
py
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort()
lo, hi = 0, len(people) - 1
boats = 0
while lo <= hi:
if people[lo] + people[hi] <= limit:
lo += 1
hi -= 1
boats += 1
return boats1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
- 时间复杂度：
- 空间复杂度：
算法思路：
- 排序后用双指针，最重和最轻的人配对
- 若能同船则两人一船，否则最重的人单独一船